#include "area.h"

/** Defaultni konstruktor pro mapy s pevnym poctem anten.
 * \param o zakladni nastaveni mapy
 * \param cell_cnt pocet anten na mape
 */
Area::Area(Options * o, int cell_cnt): general(o), calls(0) {
	freq_avail = 0;
	freq_avail_saved = 0;
	reuse_distances = 0;
	reuse_size = 0;
	setCellCount(cell_cnt);
}

/** Defaultni konstruktor pro mapy s poctem anten zavislym na nastaveni.
 * \param o zakladni nastaveni mapy
 */
Area::Area(Options * o): general(o), calls(0) {
	freq_avail = 0;
	freq_avail_saved = 0;
	reuse_distances = 0;
	reuse_size = 0;
	CELLS_CNT = 0;
	freq_dist = NULL;
	cells = NULL;
}

/** Nastavi pocet anten a alokuje potrebne datove struktury.
 * \param cell_cnt pocet anten na mape
 */
void Area::setCellCount(int cell_cnt) {
	CELLS_CNT = cell_cnt;
	cells = new Cell[CELLS_CNT];
	freq_dist = new int[CELLS_CNT * CELLS_CNT];
}

/** Defaultni destruktor, zrusi vsechnu naalokovanou pamet.
 */
Area::~Area() {
	if (calls != 0)	{
		delete[] calls;
		delete[] calls_saved;
		delete[] calls_sorted;
	}
	if (CELLS_CNT != 0) {
		delete[] freq_dist;
		delete[] cells;
	}
	if (freq_avail)	delete[] freq_avail;
	if (freq_avail_saved) delete[] freq_avail_saved;
	delete general;
}

/** Nacte pocty pozadavku na vysilace pro jednotlive anteny.
 * Pocty pozadavku ulozi a naalokuje potrebne datove struktury.
 * \param demands pole s pocty vysilacu na jednotlivych antenach
 */
void Area::readDemands(int * demands) {
	size = 0;
	for (int i = 0; i < CELLS_CNT; ++i) {
		cells[i].set(demands[i], size);
		size += demands[i];
	}
	initialize(size);
}

/** Naalokuje struktury pro zadany pocet vysilacu a nastavi prislusnost jednotlivych vysilacu k antenam.
 * \param size pocet vysilacu
 */
void Area::initialize(int size) {
	calls = new int[size];
	for (int i = 0; i < size; ++i) {
		calls[i] = 0;
	}
	calls_saved = new int[size];
	calls_owner = new int[size];
	calls_sorted = new int[size];
	cell_min = new int[size];
	cell_min_saved = new int[size];
	// assign call owners
	int j = 0;
	for (int i = 0; i < size; ++i) {
		cell_min[i] = 1;
		if (cells[j].index + cells[j].demand == i) ++j;
		calls_owner[i] = j;
	}
}

/** Spocita minimalni frekvencni vzdalenosti mezi vsemi antenami. 
 * \param r vektor znovupouzitenych vzdalenosti
 * \param r_size pocet prvku vektoru r
 */
void Area::countDistances(double * r, int r_size) {
	if (r != 0) {
		if (reuse_distances) delete[] reuse_distances;
		reuse_distances = r;
		reuse_size = r_size;
	}
	int i, j, k, fd;
	for (i = 0; i < reuse_size; ++i) {
		general->Log() << i << ": " << reuse_distances[i] << ", ";
	}
	general->Log() << std::endl;
	double dist;
	for (i = 0; i < CELLS_CNT; ++i) {
		for (j = i; j < CELLS_CNT; ++j) {
			fd = reuse_size - 1;
			dist = sqrt(double(SQR(cells[i].x - cells[j].x) + SQR(cells[i].y - cells[j].y)));
			//general->Log() << "Distance " << i << "[" << cells[i].x << ", " << cells[i].y << "] a " << j << "[" << cells[j].x << ", " << cells[j].y << "] = " << dist << ", na druhou " << sqr(cells[i].x - cells[j].x) + sqr(cells[i].y - cells[j].y) << std::endl;
			for (k = 0; k < reuse_size; ++k) {
				if (dist > reuse_distances[k] - EPSILON) {
					fd = k;
					break;
				}
			}
			setFrequencyDistance(i, j, fd);
			// muzu jeste pridat do seznamu omezovanych
			if (fd != 0) {
				if (dist > 1 - EPSILON && dist < 1 + EPSILON) {
					cells[i].neighbours.push_back(j);
					cells[j].neighbours.push_back(i);
				}
				cells[i].addConstraint(j);
				if (i != j) cells[j].addConstraint(i);
			}
		}
	}
}


/** Vrati minimalni frekvencni vzdalenost mezi zadanymi antenami.
 * \param i index prvni anteny
 * \param j index druhe anteny
 * \return minimalni frekvencni vzdalenost mezi antenami i a j, |f(i) - f(j)| >= vracena hodnota
 */
int Area::frequencyDistance(int i, int j) {
	return freq_dist[i * CELLS_CNT + j];
}

/** Nastavi zadanou minimalni frekvencni vzdalenost pro zadane anteny. 
 * \param i index prvni anteny
 * \param j index druhe anteny
 * \param d minimalni frekvencni vzdalenost
 */
void Area::setFrequencyDistance(int i, int j, int d) {
	freq_dist[i * CELLS_CNT + j] = d;
	freq_dist[j * CELLS_CNT + i] = d;
}

/** Spocte a nastavi maximalni mozny pocet vyuzitych frekvenci. Spocita horni odhad poctu frekvenci jako pocet_anten * frekvencni_vzdalenost_na_jedne_antene 
 * \return spocteny horni odhad poctu frekvenci
 */
int Area::getMaxFrequencies() {
	int max_frequencies = size * reuse_size;
	setFrequencyCount(max_frequencies);
	return max_frequencies;
}

/** Nastavi maximalni vyuzitelny pocet frekvenci a naalakuje prislusne datove struktury. 
 * \param f pocet frekvenci
 */
void Area::setFrequencyCount(int f) {
	// zmeni pocet frekvenci na f -> pokud uz nejake frekvence byly prideleny a mam ulozenou masku pridelitelnych frekvenci, tak ji prenesu dal
	bool * f_avail = new bool[f * CELLS_CNT + 1];
	bool * f_avail_saved = new bool[f * CELLS_CNT + 1];
	int free_start = 1;
	if (freq_avail) {
		if (frequencies > f) free_start = f + 1;
		else free_start = frequencies + 1;
		for (int i = 0; i < CELLS_CNT; ++i) {
			for (int j = 1; j < free_start; ++j) {
				f_avail[i * f + j] = freq_avail[i * frequencies + j];
				f_avail_saved[i * f + j] = freq_avail_saved[i * frequencies + j];
			}
		}
		delete[] freq_avail;
		delete[] freq_avail_saved;
	}

	frequencies = f;
	// nastavim povoleno novym frekvencim
	for (int j = free_start; j < frequencies + 1; ++j) {
		for (int i = 0; i < CELLS_CNT; ++i) {
			f_avail[i * frequencies + j] = true;
			f_avail_saved[i * frequencies + j] = true;
		}
	}
		
	// prepocitat posledni ruseni - u frekvenci, ktere zasahuji mimo moje pasmo!
	int * max_el, d, end, forbid;
	for (int cell = 0; cell < CELLS_CNT; ++cell) {
		// najdu max call a podle toho potom posoudim, jestli mne ovlivnuje
		if (*(max_el = std::max_element(calls + cells[cell].index, calls + cells[cell].index + cells[cell].demand)) != 0) {
			if (free_start - *max_el < reuse_size - 1) {
				for (std::vector<int>::const_iterator i = cells[cell].constraints.begin(); i != cells[cell].constraints.end(); ++i) {
					d = frequencyDistance(cell, *i) - 1;
					end = MIN(*max_el + d, frequencies);
					for (forbid = free_start; forbid <= end; ++forbid) {
						f_avail[forbid + (*i) * frequencies] = false;
					}
				}
			}
		}
		if (*(max_el = std::max_element(calls_saved + cells[cell].index, calls_saved + cells[cell].index + cells[cell].demand)) != 0) {
			if (free_start - *max_el < reuse_size - 1) {
				for (std::vector<int>::const_iterator i = cells[cell].constraints.begin(); i != cells[cell].constraints.end(); ++i) {
					d = frequencyDistance(cell, *i) - 1;
					end = MIN(*max_el + d, frequencies);
					for (forbid = free_start; forbid <= end; ++forbid) {
						f_avail_saved[forbid + (*i) * frequencies] = false;
					}
				}
			}
		}
	}

	freq_avail = f_avail;
	freq_avail_saved = f_avail_saved;
}


/** Setridi frekvence prirazene jednotlivym antenam - hezci tisk.
 */
void Area::sort() {
	for (int i = 0; i < CELLS_CNT; ++i) {
		std::sort(calls + cells[i].index, calls + cells[i].index + cells[i].demand);
	}
}

/** Setridi frekvence v aktualnim prirazenim a ulozi je do pomocneho pole, aktualni prirazeni neni zmeneno. 
 * \return serazene prirazeni frekvenci (frekvence prirazene jedne antene jsou serazeny od nejmensi k nejvetsi)
 */
int * Area::sortedCalls() {
	memcpy(calls_sorted, calls, size * sizeof(int));
	for (int i = 0; i < CELLS_CNT; ++i) {
		std::sort(calls_sorted + cells[i].index, calls_sorted + cells[i].index + cells[i].demand);
	}
	return calls_sorted;
}

/** Vypise do logu minimalni frekvencni vzdalenosti mezi jednotlivymi antenami.
 */
void Area::printFrequencyDistances() {
	general->Log() << "FD||";
	for (int i = 0; i < CELLS_CNT; ++i) {
		general->Log() << std::setw(2) << i << "|";
	}
	general->Log() << std::endl;
	general->Log() << std::string(CELLS_CNT * 3 + 4, '-') << std::endl;

	for (int i = 0; i < CELLS_CNT; ++i) {
		if (i < 10) general->Log() << " ";
		general->Log() << i << "|| "; 
		for (int j = 0; j < CELLS_CNT; ++j) {
			general->Log() << frequencyDistance(i, j) << "| ";
		}
		general->Log() << std::endl;
	}
}

/** Vypise do logu vsechna omezeni vznikla jednotlivymi omezujicimi podminkami (v podstate graf ruseni).
 */
void Area::printConstraints() {
	/* vypis sousedu se kterymi mam nejaky constraint */
	for (int i = 0; i < CELLS_CNT; ++i) {
		general->Log() << "Sousedi " << i << ": ";
		for (std::vector<int>::const_iterator n = cells[i].constraints.begin(); n != cells[i].constraints.end(); ++n) {
			general->Log() << std::setw(3) << *n << " (" << frequencyDistance(i, *n) << ")";
		}
		general->Log() << std::endl;
	}
}

/** Vrati index anteny pro zadany vysilac. 
 * \param call index vysilace
 * \return index anteny
 */
int Area::findCell(int call) {
	return calls_owner[call];
}

/** Zjisti index anteny pro zadany vysilac. 
 * \param call index vysilace
 * \param cell index anteny, vystupni parametr (pokud je -1, tak je vyplnen)
 */
void Area::findCell(int call, int &cell) {
	if (cell == -1) {
		cell = calls_owner[call];
	}	
}

/** Zkontroluje zda je povolene vysilaci priradit frekvenci.
 * \param call index vysilace
 * \param freq prirazovana frekvence
 * \param cell index anteny
 * \return true pokud je mozne frekvenci vysilaci priradit
 */
bool Area::checkChange(int call, int freq, int cell) {
	findCell(call, cell);
	return freq_avail[cell * frequencies + freq];
}

/** Zkontroluje korektnost spocteneho prirazeni.
 * \param max maximalni povolena pouzita frekvence
 * \return 0 pokud je vse v poradku, -1 pri nedodrzeni minimalni frekvencni vzdalenosti, -2 pri vyuziti vetsi frekvence nez je max, > 0 pocet vysilacu bez frekvence
 */
int Area::isAssignmentCorrect(int max) {
	int unassigned = 0;
	for (int i = 0; i < size; ++i) {
		if (calls[i] == 0) {
			++unassigned;
			continue;
		}
		else if (calls[i] > max) {
			return -2;
		}
		/* check all other assigned frequencies and constraints */
		for (int n = 0; n < size; ++n) {
			if (n == i) continue;
			/* realfrequency distance is smaller than the needed one */
			if (abs(calls[i] - calls[n]) < frequencyDistance(findCell(i), findCell(n))) return -1;
		}
	}
	return unassigned;
}

/** Priradi vybranemu vysilaci danou frekvenci. Nejprve zkontroluje, zda je toto prirazeni mozne. Po prirazeni prepocita povolene frekvence vsem antenam.
 * \param call index vysilace
 * \param freq prirazovana frekvence
 * \param cell index anteny
 * \return true pokud se povedlo frekvenci vysilaci priradit
 */
bool Area::assignCall(int call, int freq, int cell) {
	findCell(call, cell);
	int old = calls[call];
	if (checkChange(call, freq, cell)) {
		// nastavit call na freq
		calls[call] = freq;
		// a potom nastavit vznikle omezeni na vsech bunkach, ktere omezuju
		int forbid, d, end;
		// vsechny bunky, ktere muzu ohrozit - u kazde si pamatuju seznam sousedu
		for (std::vector<int>::const_iterator i = cells[cell].constraints.begin(); i != cells[cell].constraints.end(); ++i) {
			d = frequencyDistance(cell, *i) - 1;
			end = MIN(frequencies, freq + d);
			if (freq - d <= cell_min[*i] && freq + d >= cell_min[*i]) { // nastavim minimum
				cell_min[*i] = freq + d + 1;
			}
			for (forbid = MAX(freq - d, 1); forbid <= end; ++forbid) {
				freq_avail[forbid + (*i) * frequencies] = false;
			}
		}
		return true;
	}
	else {
		// calls[call] = old;
		return false;
	}
}

/** Priradi frekvenci jednomu vysilaci na vybrane antene.
 * \param cell index anteny
 * \param freq prirazovana frekvence
 * \return true pokud se povedlo priradit
 */
bool Area::assignCell(int cell, int freq) {
	int call;
	for (call = cells[cell].index; call <= cells[cell].demand && calls[call] != 0; ++call);
	if (call > cells[cell].demand) return false;
	return assignCall(call, freq, cell);
}

/** Ulozeni aktualni prirazeni frekvenci.
 */
void Area::save() {
	for (int i = 0; i < size; ++i) {
		calls_saved[i] = calls[i];
		cell_min_saved[i] = cell_min[i];
	}
	for (int i = 0; i < frequencies * CELLS_CNT + 1; ++i) {
		freq_avail_saved[i] = freq_avail[i];
	}
}

/** Nacte prirazeni z naposledy ulozeneho.
 */
void Area::load() {
	for (int i = 0; i < size; ++i) {
		cell_min[i] = cell_min_saved[i];
		calls[i] = calls_saved[i];
	}
	for (int i = 0; i < frequencies * CELLS_CNT + 1; ++i) {
		freq_avail[i] = freq_avail_saved[i];
	}
}

/** Vycisti prirazeni frekvenci. Zadnemu vysilaci nebude prirazena frekvence a vsechny anteny budou mit povoleny vsechny frekvence.
 */
void Area::clear() {
	for (int i = 0; i < size; ++i) {
		cell_min[i] = 1;
		calls[i] = 0;
	}
	for (int i = 0; i < frequencies * CELLS_CNT + 1; ++i) {
		freq_avail[i] = true;
	}
	save();
}
